Heaps: The heapify Algorithm

The `heapify` process works backwards from the last non-leaf node up to the root, fixing the heap property at each step.

The key idea is to assume that the subtrees rooted at a node's children are already valid heaps before processing the node itself.
For each node, we call a bubbleDown (or `siftDown`) function to sink the node to its correct position, ensuring the heap property is satisfied for the subtree rooted at that node.
By starting from the last non-leaf node and moving upwards, we guarantee this assumption holds true, efficiently building the heap in-place.

Last Non-Leaf Node

In a zero-indexed array representation of a heap with `n` elements, the last node that has children (the last non-leaf node) is always located at index `floor(n / 2) - 1`.

Initial state

# Python implementation of build_heap
def build_heap(array):
    n = len(array)
    # Start from the last non-leaf node and move up
    start_index = (n // 2) - 1
    
    for i in range(start_index, -1, -1):
        bubble_down(array, i)
    
    return array